/*
 * @lc app=leetcode.cn id=234 lang=typescript
 *
 * [234] 回文链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function isPalindrome(head: ListNode | null): boolean {
  if (head === null) return false;
  let slow = head;
  let fast = head;
  // 快慢指针，寻找中间位置
  // 这里找的是中间位置的前一个节点
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  const reverse = (head: ListNode): ListNode => {
    const ans = new ListNode();
    let p = head;
    let q = null;
    while (p) {
      q = p.next;
      p.next = ans.next;
      ans.next = p;
      p = q;
    }
    return ans.next;
  };

  // slow节点就是中位节点，反转中位后的节点
  slow.next = reverse(slow.next);

  // 双指针比较
  let p = head;
  let q = slow.next;
  while (q) {
    if (p.val !== q.val) return false;
    p = p.next;
    q = q.next;
  }

  return true;
}
// @lc code=end
